package com.testProject.test.Sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        merge(arr,0,arr.length-1);
        System.out.println( Arrays.toString(arr));
    }

    public static void merge(int[] nums,int left,int right){
        if(left>=right) return;
        int mid=(left+right)/2;
        merge(nums,left,mid);
        merge(nums,mid+1,right); //先对nums进行切分，切分后再进行排序，这就是一个后续遍历
        mergeSort(nums,left,mid,right);
    }

    public static void mergeSort(int[] nums,int left,int mid,int right){
        int[] temp=new int[right-left+1];
        int i=left;int j=mid+1,k=0;
        while (i<=mid&&j<=right){
            temp[k++]=nums[i]<nums[j]?nums[i++]:nums[j++];
        }
        while (i<=mid){
            temp[k++]=nums[i++];
        }
        while (j<=right){
            temp[k++]=nums[j++];
        }
        for(int a=left;a<=right;a++){
            nums[a]=temp[a-left];
        }
    }
}
